package 剑指offer;

import java.util.Arrays;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:34:38 
* @Description：
* 
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法
*/
public class $9变态跳台阶 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		
		
		System.out.println(n<<1);
		System.out.println(n>>1);
		System.out.println(n>>>1);
		System.out.println("===============");
		System.out.println(JumpFloorII(n));
		System.out.println( JumpFloorII2(n));
		System.out.println(JumpFloorII3(n));
	}
	
	//不同于上面的跳1，2个台阶，可以是1-N次
	/*
	 *可以推导出  f(n)=f(n-1)+f(n-2)+f(n-3)+  --- +f(2) +f(1)
	 f(n-1)=f(n-2)+f(n-3)+  ++ f(2)+f(1)
	 两式相减可知： f(n)=2f(n-1)
	 */
	
public  static int JumpFloorII(int target) {
	return 1<<(target-1);
    }


//dp动态规划
	public static int JumpFloorII2(int target) {
		if (target <= 2) {
			return target;
		}
		int[] dp = new int[target + 1];

		Arrays.fill(dp, 1); 							// 初始化每一种都可以直接从 0 跳到 n
		dp[0] = 0; 									// 从 0 跳到 0 为 0 种，因为 n = 0，没法跳
		for (int i = 2; i <= target; i++) {
			for (int j = i - 1; j >= 1; j--) {
				dp[i] += dp[j]; 						// 第 n 个状态是由前 n - 1 种状态推导出来，就是累加！
			}
		}
		return dp[target];
	}
	
	  // 从3开始：(n-2)*2 + (n-1)
    // n: 0 1 2 3 4 05 06
    // v: 1 1 2 4 8 16 32
	
	public static int JumpFloorII3(int target) {
		if (target<=2) {
			return target;
		}
		
		int cur=1,next=2;
		while (--target>0) {
			int temp=next;
			next+=cur*2;
					cur=temp;
		}
		return cur;
	}
}
